LinkedList = LinkedList or {}

LinkedList.Node = LinkedList.Node or {}
local Node = LinkedList.Node


function Node.new(v2)
    local inst = {
        _cname = "lang.LinkedList.Node",
        _list = nil,
        _n = nil,
        _p = nil,
    }
    
    local v = v2
    
    function inst:value()
        return v
    end
    
    function inst:setValue(v2)
        v = v2
    end
    
    function inst:next()
        return self._n
    end
    
    function inst:prev()
        return self._p
    end
    
    function inst:list()
        return self._list
    end

    return inst
end




function LinkedList.new()
    local inst = {
        _cname = "lang.LinkedList"
    }
    
    local first = nil
    local last = nil
    local len = 0
    
    function inst:count()
        return len
    end
    
    function inst:clear()
        first = nil
        last = nil
        len = 0
    end
    
    function inst:contains(v)
        if 0 == len then return false end
        if "lang.LinkedList.Node" == v._cname then
            assert(self == v._list, "remove: not my node")
            local n_cur = first
            while nil ~= n_cur do
                if n_cur == v then
                    return true
                end
                n_cur = n_cur:next()
            end
        else
            local n_cur = first
            while nil ~= n_cur do
                if n_cur:value() == v then
                    return true
                end
                n_cur = n_cur:next()
            end
        end

        return false
    end
    
    function inst:copyTo(dst)
    end

    local function removeNode(self, n_cur)
        if n_cur == first then
            self:removeFirst()
        elseif n_cur == last then
            self:removeLast()
        else
            local n_left = n_cur._p
            local n_right = n_cur._n

            n_cur._p = nil
            n_cur._n = nil
            n_cur._list = nil
            len = len - 1

            n_left._n = n_right
            n_right._p = n_left
        end
    end
    
    function inst:remove(v)
        if 0 == len then return false end
        if "lang.LinkedList.Node" == v._cname then
            assert(self == v._list, "remove: not my node")
            local n_cur = first
            while nil ~= n_cur do
                if n_cur == v then
                    removeNode(self, n_cur)
                    return true
                end
                n_cur = n_cur:next()
            end
        else
            local n_cur = first
            while nil ~= n_cur do
                if n_cur:value() == v then
                    removeNode(self, n_cur)
                    return true
                end
                n_cur = n_cur:next()
            end
        end

        return false
    end
    
    function inst:first()
        if 0 == len then return nil end
        return first:value()
    end
    
    function inst:last()
        if 0 == len then return nil end
        return last:value()
    end
    
    function inst:addAfter(node, v)
        assert("lang.LinkedList.Node" == node._cname, "addAfter: invalid node type")
        assert(self == node._list, "addAfter: not my node")
        local n_cur = nil
        if "lang.LinkedList.Node" == v._cname then
            assert(nil == v._list, "addAfter: already add to some LinkedList")
            n_cur = v
        else
            n_cur = Node.new(v)
        end
        n_cur._list = self

        local n_left = node
        if last == n_left then
            n_left._n = n_cur
            --最右
            n_cur._p = n_left
            n_cur._n = nil
            last = n_cur
        else
            local n_right = n_left._n

            n_left._n = n_cur
            --中
            n_cur._p = n_left
            n_cur._n = n_right

            n_right._p = n_cur
        end
        len = len + 1
    end
    
    function inst:addBefore(node, v)
        assert("lang.LinkedList.Node" == node._cname, "addBefore: invalid node type")
        assert(self == node._list, "addBefore: not my node")

        local n_cur = nil
        if "lang.LinkedList.Node" == v._cname then
            assert(nil == v._list, "addBefore: already add to some LinkedList")
            n_cur = v
        else
            n_cur = Node.new(v)
        end
        n_cur._list = self

        local n_right = node
        if first == n_right then
            --最左
            n_cur._p = nil
            n_cur._n = n_right
            first = n_cur

            n_right._p = n_cur
        else
            local n_left = n_right._p

            n_left._n = n_cur
            --中
            n_cur._p = n_left
            n_cur._n = n_right

            n_right._p = n_cur
        end
        len = len + 1
    end
    
    function inst:addFirst(v)
        local n_cur = nil
        if "lang.LinkedList.Node" == v._cname then
            assert(nil == v._list, "addFirst: already add to some LinkedList")
            n_cur = v
        else
            n_cur = Node.new(v)
        end
        n_cur._list = self
        if 0 == len then
            first = n_cur
            last = n_cur
        else
            local n_right = first
            --最左
            n_cur._p = nil
            n_cur._n = n_right
            first = n_cur

            n_right._p = n_cur
        end
        len = len + 1
    end
    
    function inst:addLast(v)
        local n_cur = nil
        if "lang.LinkedList.Node" == v._cname then
            assert(nil == v._list, "addLast: already add to some LinkedList")
            n_cur = v
        else
            n_cur = Node.new(v)
        end
        n_cur._list = self
        if 0 == len then
            first = n_cur
            last = n_cur
        else
            local n_left = last

            n_left._n = n_cur
            --最右
            n_cur._p = n_left
            n_cur._n = nil
            last = n_cur
        end
        len = len + 1
    end

    function inst:removeFirst()
        if 0 == len then return false end
        local n_cur = first
        local n_right = first._n

        n_cur._p = nil
        n_cur._n = nil
        n_cur._list = nil
        len = len - 1

        if 0 == len then
            first = nil
            last = nil
        else
            n_right._p = nil
            first = n_right
        end
        return true
    end
    
    function inst:removeLast()
        if 0 == len then return false end
        local n_left = last._p
        local n_cur = last

        n_cur._p = nil
        n_cur._n = nil
        n_cur._list = nil
        len = len - 1

        if 0 == len then
            first = nil
            last = nil
        else
            n_left._n = nil
            last = n_left
        end
        return true
    end
    
    function inst:find(v)
        if 0 == len then return nil end
        local n_cur = first
        while n_cur ~= nil do
            if n_cur:value() == v then
                return n_cur
            end
            n_cur = n_cur:next()
        end
        return nil
    end
    
    function inst:findLast(v)
        if 0 == len then return nil end
        local n_cur = last
        while n_cur ~= nil do
            if n_cur:value() == v then
                return n_cur
            end
            n_cur = n_cur:prev()
        end
        return nil
    end

    function inst:__tostring()
        if 0 == len then return "" end

        local strTb = {}
        local n_cur = first
        while n_cur ~= nil do
            local v = n_cur:value()
            table.insert(strTb, (nil == v) and "nil" or tostring(v))
            n_cur = n_cur:next()
        end
        return table.concat(strTb, ",")
    end

    function inst:__len()
        return len
    end

    function inst:__index(k)
        error("LinkedList: invalid member: " .. k)
    end

    function inst:__newindex(k, v)
        error("LinkedList: new member error: " .. k)
    end
    
    setmetatable(inst, inst)
    return inst
end

function LinkedList.__call()
    return LinkedList.new()
end
setmetatable(LinkedList, LinkedList)


local function TestAdd()
    local l = LinkedList()
    l:addLast("one")
    assert(1 == l:count(), "add error")
    assert(l:contains("one"), "add error")
    
    l:addLast("two")
    assert(2 == l:count(), "add error")
    assert(l:contains("one"), "add error")
    assert(l:contains("two"), "add error")

    tostring(l)

    l:addFirst("zero")
    assert(3 == l:count(), "add error")
    assert(l:contains("zero"), "add error")
    assert(l:contains("one"), "add error")
    assert(l:contains("two"), "add error")

    l:addLast("three")
    assert(4 == l:count(), "add error")
    assert(l:contains("zero"), "add error")
    assert(l:contains("one"), "add error")
    assert(l:contains("two"), "add error")
    assert(l:contains("three"), "add error")
end

local function TestRemove()
    local l = LinkedList()
    l:addLast("one")
    l:remove("one")
    assert(0 == l:count(), "remove error")
    assert(false == l:contains("one"), "remove error")
    assert(false == l:removeFirst(), "remove error")
    assert(false == l:removeLast(), "remove error")

    l:addFirst("one")
    l:addFirst("zero")
    assert(l:removeFirst(), "remove error")
    assert("one" == l:first(), "remove error")
    assert("one" == l:last(), "remove error")
    assert(l:removeLast(), "remove error")
    assert(false == l:removeFirst(), "remove error")
    assert(false == l:removeLast(), "remove error")

    l:addFirst("one")
    l:addLast("two")
    l:addLast("three")
    l:addLast("four")
    l:remove("two")
    assert("one" == l:first(), "remove error")
    assert("four" == l:last(), "remove error")
    assert(3 == l:count(), "remove error")
end

local function TestFind()
    local l = LinkedList()

    l:addFirst("one")
    l:addLast("two")
    l:addLast("three")
    l:addLast("four")

    assert(nil ~= l:find("one"), "find error")
    assert(nil == l:find("five"), "find error")
end

--TestAdd()
--TestRemove()
--TestFind()


